#include "main/utils.h"
using namespace std;

int core(string str_n) {
  int size = str_n.size();
  long first_digit = stol(str_n.substr(0, 1));

  if (str_n.size() == 1 && first_digit == 0)
    return 0;
  if (str_n.size() == 1 && first_digit > 0)
    return 1;

  long other_digit = stol(str_n.substr(1));
  int num_first_digit = 0;
  if (first_digit > 1) {
    num_first_digit = pow(10, size - 1);
  } else if (first_digit == 1) {
    num_first_digit = other_digit + 1;
  }

  int num_other_digit = first_digit * (size - 1) * pow(10, size - 2);

  string other_str = str_n.substr(1);
  int num_recursive = core(other_str);

  return num_first_digit + num_other_digit + num_recursive;
}

int numberOf1Between1AndN(int n) {
  string str_n = to_string(n);
  return core(str_n);
}

int main() {
  int n = 21345;
  int ret = numberOf1Between1AndN(n);
  cout << "The number of 1 between and 21345: " << ret << " expected: 18821" << endl;

  return 0;
}
